Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 89/115

Q: In a leftist heap, all the operations should be performed on?
A. left path
B. centre path
C. right path
D. root 
Solution: All the operations are performed on the right path because right paths are short. However, insertion and merges cannot be performed on the right path.
Q: What would be the result if the left subtree of the root has a null path length of 1 and the right subtree has a null path length of 2?
A. merge occurs without violation
B. violation at left subtree
C. violation at right subtree
D. violation at the root
Solution: When two leftist heaps are merged, if the left subtree of the root has a null path length of 1 and the right subtree has a null path length of 2, leftist property is violated at the root.
Q: What happens if the null path length is not updated?
A. error occurs
B. all null path lengths will be 0
C. all null path lengths will be -1
D. all null path lengths will be 1
Solution: While performing insertion via merge operation in a leftist heap, if the null path length is not updated, all null path lengths will be 0.
Q: What is the time taken to delete a minimum element in a leftist heap?
A. O(N)
B. O(N log N)
C. O(log N)
D. O(M log N)
Solution: The time taken to delete a minimum element in a leftist heap is mathematically found to be O(log N).
Q: In what time can a leftist heap be built?
A. O(N)
B. O(N log N)
C. O(log N)
D. O(M log N)
Solution: The mathematical calculation yields a result that, a leftist heap can be built in O(N) time by building a binary heap.
Q: ___________ is a self-adjusting version of a leftist heap.
A. Rightist heap
B. Skew heap
C. d-heap
D. Binary heap
Solution: A skew heap is a self-adjusting version of a leftist heap and it is simpler to implement.
Q: The worst case running time of all operations in a skew heap is given as?
A. O(N)
B. O(N log N)
C. O(N2)
D. O(M log N)
Solution: The worst case running time of all operations in a skew heap is mathematically found to be O(N).
Q: What is the amortized cost per operation of a skew heap?
A. O(N)
B. O(N log N)
C. O(N2)
D. O(log N) 
Solution: The amortized cost per operation of a skew heap is O(log N) since the worst case analysis of skew heap is O(N) and splay tree is O(M log N).

You Have Score    /8